package leetcode.hot100;

import leetcode.tester.Tester;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.stream.Collectors;

/**
 * 438. 找到字符串中所有字母异位词
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author Liu Yicong
 * @date 2025/10/14
 */
public class Hot9SwinFindAnagrams {
	public static void main(String[] args) throws IOException {
		// 读取文件
		List<String> content = Files.readAllLines(Paths.get("src/data/Hot9SwinFindAnagrams.txt"));
		String s = content.get(0);
		String p = content.get(1);
		List<Integer> ans = Arrays.stream(content.get(2).replaceAll("[\\[\\]]", "").split(","))
				.map(String::trim)
				.mapToInt(Integer::parseInt).boxed()
				.collect(Collectors.toList());

		Object[][] inputs = {
				new Object[]{"cbaebabacd", "abc"},
				new Object[]{"abab", "ab"},
				new Object[]{"baa", "aa"},
				new Object[]{s, p}
		};
		Object[] outputs = {
				Arrays.asList(0, 6),
				Arrays.asList(0, 1, 2),
				List.of(1),
				ans
		};

		Tester.test(Tester.wrap(new Hot9SwinFindAnagrams()::findAnagrams), inputs, outputs);
		Tester.test(Tester.wrap(new Hot9SwinFindAnagrams()::findAnagramsOpt), inputs, outputs);
	}

	/**
	 * 一个非常直观的方法：为每个窗口设置一个Map
	 */
	public List<Integer> findAnagrams(String s, String p) {
		List<Integer> result = new ArrayList<>();
		int n = s.length();
		int winSize = p.length();  // 窗口大小
		if (winSize > n) {
			return result;
		}

		Map<String, Long> pCnt = p.chars().mapToObj(c -> (char) c).
				collect(Collectors.groupingBy(String::valueOf, Collectors.counting()));

		for (int start = 0; start < n - winSize + 1; start++) {
			String sub = s.substring(start, start + winSize);
			Map<String, Long> subCnt = sub.chars().mapToObj(c -> (char) c).
					collect(Collectors.groupingBy(String::valueOf, Collectors.counting()));
			boolean flag = true;
			for (String key : subCnt.keySet()) {
				if (!Objects.equals(subCnt.getOrDefault(key, 0L), pCnt.getOrDefault(key, 0L))) {
					flag = false;
					break;
				}
			}
			if (flag) {
				result.add(start);
			}
		}
		return result;
	}

	/**
	 * 由于只可能出现小写字母，所以可以直接给这26个字母创建一个长度为26的数组，而不用为每个子串单独创建一个Map。
	 * 使用数组的好处是可以使用Arrays.equals直接判断两个数组是否相等。
	 */
	public List<Integer> findAnagramsOpt(String s, String p) {
		List<Integer> result = new ArrayList<>();
		int n = s.length();
		int winSize = p.length();  // 窗口大小
		if (winSize > n) {
			return result;
		}

		int codeA = 'a';  // 97

		int[] sCnt = new int[26];
		int[] pCnt = new int[26];
		for (int i = 0; i < winSize; i++) {
			sCnt[s.charAt(i) - codeA]++;
			pCnt[p.charAt(i) - codeA]++;
		}

		if (Arrays.equals(sCnt, pCnt)) {
			result.add(0);
		}

		for (int i = 0; i < n - winSize; i++) {
			sCnt[s.charAt(i) - codeA] -= 1;
			sCnt[s.charAt(i + winSize) - codeA] += 1;

			if (Arrays.equals(sCnt, pCnt)) {
				result.add(i + 1);
			}
		}
		return result;
	}

}
